//
//  快速排序.swift
//  Swift-LeetCode
//
//  Created by 卢悦明 on 2024/3/2.
//

import UIKit

class QuickSort: NSObject {
    var array = [Int]()
    func sort(_ array: [Int]) -> [Int] {
        self.array = array
        quick(0, array.count)
        return self.array
    }

    func quick(_ begin: Int, _ end: Int) {
        if end - begin < 2 {
            return
        }
        let mid = getPovIndex(begin, end)
        quick(begin, mid)
        quick(mid + 1, end)
        
    }
    func getPovIndex(_ begin: Int, _ end: Int) -> Int {
        let prov = array[begin]
        var end = end
        var begin = begin
        end -= 1
        while begin < end {
            while begin < end {
                if array[end] > prov {
                    end -= 1
                } else {
                    array[begin] = array[end]
                    begin += 1
                    break
                }
            }
            while begin < end {
                if array[begin] < prov {
                    begin += 1
                } else {
                    array[end] = array[begin]
                    end -= 1
                    break
                }
            }
        }
        array[begin] = prov
        return begin
    }
    
}
